package com.yun.algorithmproblem.leetcode;

import java.util.PriorityQueue;

/**
 * 1338. 数组大小减半
 * <p>
 * 给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
 * <p>
 * 返回 至少 能删除数组中的一半整数的整数集合的最小大小。
 */
public class Leetcode1338 {

    public static void main(String[] args) {
        Leetcode1338 obj = new Leetcode1338();
        int[] arr = new int[]{3,3,3,3,5,5,5,2,2,7};
        int res = obj.minSetSize(arr);
        System.out.println(res);
    }

    public int minSetSize(int[] arr) {
        int[] bucket = new int[100001];
        for (int num : arr) {
            bucket[num]++;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int num : bucket) {
            if (num != 0) {
                heap.offer(num);
            }
        }
        int res = 0;
        int sum = 0;
        while (sum * 2 < arr.length) {
            Integer poll = heap.poll();
            sum+=poll;
            res++;
        }
        return res;
    }
}


